package 区间;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;

import static MyUtils.MHUtils.*;
import static MyUtils.MHMoban.*;

public class 用最少数量的箭穿爆全部气球452 {
    @Test
    public void test() {
        int[][] p = {{10,16},{2,8},{1,6},{7,12}};
        System.out.println(findMinArrowShots(p));
    }
    int[][] g;
    public int findMinArrowShots(int[][] g) {
        this.g = g;
        Arrays.sort(g, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if(a[0]==b[0]){
                    return b[1]-a[1];
                }
                return a[0]-b[0];
            }
        });
        int count = 1;
        //公共区间
        int[] qj = new int[2];
        qj[0]=g[0][0];qj[1]=g[0][1];
        for (int i = 1; i < g.length; i++) {
            //看图，干想不可能的
            if(g[i][0] <= qj[1]){
                qj[0]=Math.max(qj[0],g[i][0]);
                qj[1]=Math.min(qj[1],g[i][1]);
            }else{
                qj[0]=g[i][0];
                qj[1]=g[i][1];
                count++;
            }
        }
        return count;
    }
}
